package com.jdaw.datastructure.recursion;

public class MiGong {
    public static void main(String[] args) {
        int[][] map=new int[8][7];
        //1表示墙，设置墙
        for(int i=0;i<7;i++){
            map[0][i]=1;
            map[7][i]=1;
            map[i][0]=1;
            map[i][6]=1;
        }
        map[3][1]=1;
        map[3][2]=1;
        map[2][2]=1;
        //输出地图情况
//        for(int i=0;i<map.length;i++){
//            for (int j=0;j<map[i].length;j++){
//                System.out.print(map[i][j]);
//                System.out.print(" ");
//            }
//            System.out.println("");
//        }
        System.out.println(setWay(map,1,1));
        for(int i=0;i<map.length;i++){
            for (int j=0;j<map[i].length;j++){
                System.out.print(map[i][j]);
                System.out.print(" ");
            }
            System.out.println("");
        }
    }

    //使用递归回溯给小球找路
    //设置地图，设置初始位置，到map[6][5]表示通路找到
    //map[i][j]为0表示路没走过，为1表示墙，为2表示通路可走，3表示已经走过
    //策略：下右上左，下面走不通走右面，右面不行上。。。，走不通再回溯
    public static boolean setWay(int[][] map,int i,int j){
        if(map[6][5]==2){
            //路已通
            return true;
        }else{
            if(map[i][j]==0){
                map[i][j]=2;//假定该点可以走通
                //开始采取策略，使用递归
                if(setWay(map,i+1,j)){
                    //左走
                    return true;
                }else if(setWay(map,i,j+1)){
                    //右走
                    return true;
                }else if(setWay(map,i-1,j)){
                    //上走
                    return true;
                }else if(setWay(map,i,j-1)){
                    //左走
                    return true;
                }else{
                    //走不通的死路
                    map[i][j]=3;
                    return false;
                }
            }else{
                return false;
            }
        }
    }
}
